﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class Node
{
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() { }

    public Node(int _val)
    {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next)
    {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
namespace BinarTtree.Connect
{
    class Connect
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            Node node = new Node(1, new Node(2, new Node(4), new Node(5), null), new Node(3, new Node(6), new Node(7), null), null);
            Connect1(node);
            Console.ReadKey();
        }

        /// <summary>
        /// BFS(层序遍历)
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static Node Connect1(Node root)
        {
            if (root==null) return root;
            Queue<Node> que = new Queue<Node>();
            que.Enqueue(root);
            while (que.Count > 0)
            {
                int size = que.Count;
                for (int i = 0; i < size; i++)
                {
                    Node node = que.Dequeue();

                    if (que.Count > 0 ) node.next = que.Peek();
                    if (i == size - 1) node.next = null;
                    if (node.left != null) que.Enqueue(node.left);
                    if (node.right != null) que.Enqueue(node.right);
                }
            }
            return root;
        }
    }
}
